export class TreeNode {
    val: number;
    left: TreeNode | null;
    right: TreeNode | null;
    constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
        this.val = val === undefined ? 0 : val;
        this.left = left === undefined ? null : left;
        this.right = right === undefined ? null : right;
    }
}
function kthSmallest(root: TreeNode | null, k: number): number {
    let result = 0;
    let count = 0;

    function inOrderTraversal(node: TreeNode | null): void {
        if (!node) return;

        // 遍历左子树
        inOrderTraversal(node.left);

        // 处理当前节点
        count++;
        if (count === k) {
            result = node.val;
            return;
        }

        // 遍历右子树
        inOrderTraversal(node.right);
    }

    inOrderTraversal(root);
    return result;
};

// 迭代
function kthSmallestIterative(root: TreeNode | null, k: number): number {
    const stack: TreeNode[] = [];
    let current = root;
    let count = 0;

    while (current !== null || stack.length > 0) {
        // 遍历到最左边的节点
        while (current !== null) {
            stack.push(current);
            current = current.left;
        }

        // 弹出栈顶节点
        current = stack.pop()!;
        count++;

        // 如果找到第k小的元素
        if (count === k) {
            return current.val;
        }

        // 转向右子树
        current = current.right;
    }

    return -1; // 如果k超出范围
}